package weekMatch.two_104;

import java.util.Arrays;

public class LeeCode_03 {
    public static void main(String[] args) {
//        System.out.println(maximumOr(new int[]{12, 9}, 1));
//        System.out.println(maximumOr(new int[]{8, 1, 2}, 2));
//        System.out.println(maximumOr(new int[]{24, 29, 26}, 1));
        System.out.println(maximumOr(new int[]{10, 8, 4}, 1));
//        System.out.println(29 | 26);
    }
    private static long maximumOr(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long max = nums[n - 1];
        long tmp = 1;
        while (tmp < max){
            tmp *= 2;
        }
        tmp /= 2;
        long ans = 0;
        long[] dp = new long[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] | nums[i];
        }
        long[] dp2 = new long[n];
        dp2[n - 1] = nums[n - 1];
        for(int i = n - 2;i >= 0; i--){
            dp2[i] = nums[i] | dp2[i + 1];
        }
        for(int i = n - 1; i >= 0; i--){
            if (nums[i] >= tmp){
                long pre = i - 1 < 0 ? 0 : dp[i - 1];
                long aft = i + 1 >= n ? 0 : dp2[i + 1];
                max = nums[i];
                for (int j = 0; j < k; j++) {
                    max *= 2;
                }
                ans = Math.max(ans, max | pre | aft);
            }
        }
        return ans;
    }
}
